package linked;

import java.util.HashSet;
import java.util.Set;

/**
 * 142. 环形链表 II
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。
 * 如果链表无环，则返回 null。
 * <p>
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 不允许修改 链表。
 */
public class Problem_142 {

    /**
     * 方法一：哈希表
     * 挨个遍历链表节点，每遍历到一个节点时，判断该节点此前是否被访问过。
     * 具体做法:
     * 我们可以使用哈希表来存储所有已经访问过的节点。
     * 每到一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，且此节点是进入环的第一个节点，直接返回该节点；
     * 否则，就将该节点加入到哈希表中，继续遍历下一个节点 并重复上述过程。
     * 若可以遍历到链表的末尾，则表示链表无环，最后返回null即可。
     */
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet();
        ListNode listNode = head;
        while (listNode != null) {
            if (set.contains(listNode)) {
                return listNode;
            }
            set.add(listNode);
            listNode = listNode.next;
        }
        return null;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
